/*
注意：
由于识别过程中存在|和&
故采用$代替|
@代替&
[代替(
]代替)
^代替*
*/
#include<bits/stdc++.h>
#include <fstream>
#include <cassert>
using namespace std;

const int OPERANDS = 1; // 操作符
const int OPERATOR = 2; // 运算符
const int ILLEGAL_CHAR = -1;  // 非法字符
const int maxn = 1e5 + 5; //最多处理的单词个数


//                    关键字 运算符 界符 标识符  整数
string name[6] = {"KW", "OP", "SE", "IDN", "FLOAT", "INT"};
string kw[9] = {"", "int", "void", "return", "const", "main", "float", "if", "else"};
string op[16] = {"", "+", "-", "*", "/", "%", "=", ">", "<", "==", "<=", ">=", "!=", "&&", "||"};
string se[7] = {"", "(", ")", "{", "}", ";", ","};
string number[29] = {"0","1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26", "27", "28"};
char isus[20] = {'+', '-', '*', '/', '%', '=', '>', '<', '=', '&', '|', '!', '{', '}', '(', ')', ';', ',', '?'};

int lll; //行数
string line[maxn];

int length; //按空格区分的单词
string letter[maxn]; //从文件中取出来的字符

int len; //有用字符
string word[maxn]; //处理的标识符
string kind[maxn]; //标识符种类
string id[maxn]; // 标识符序号或值
string pdid[maxn];

map<string, string> mp; // 存储每一种标识符对应的编号
//初始化map
void init() {
	int cnt = 0;
    for (int i = 1; i < 9; i ++) {
        mp[kw[i]] = number[++ cnt];
    }
    for (int i = 1; i < 15; i ++) {
        mp[op[i]] = number[++ cnt];
    }
    for (int i = 1; i < 7; i ++) {
        mp[se[i]] = number[++ cnt];
    }
    mp["!"] = "0";
}

//读入文件,按照空格分割单词
void read(string fi) {
	lll = len = length = 0;
	string file = fi;
    ifstream infile; 
    infile.open(file.data());   
    assert(infile.is_open());  

    string s;
    while(getline(infile, s)) {
        line[++ lll] = s;//每一行字符存于line数组
    }
    for (int i = 1; i <= lll; i ++) {
    	string s = line[i];//令s为每一行字符串
    	//处理注释
    	if (s.substr(0, 2) == "//") continue;
    	if (s.substr(0, 2) == "/*") {
    		for (int j = i; j <= lll; j ++) {
    			int l = line[j].size();
    			if (l >= 2 && line[j].substr(l - 2, 2) == "*/") {//j增大，直到注释结束
    				i = j;
    				break;
    			}
    		}
    		continue;
    	}
    	//以空格为区分，初步划分词
    	string t = "";
    	for (int j = 0; j < (int)s.size(); j ++) {
    		if (s[j] == ' ' || s[j] == '\t') {//\t为水平制表符 横向跳跃8空格
    			if (t != "") {
    				letter[++ length] = t;
    			} 
    			t = "";
    		}else {
    			t = t + s[j];
    		}
    	}
    	if (t != "") letter[++ length] = t;
    }

    infile.close();             //关闭文件输入流 
}


//获取字符类型
int get_chartype(char c) {
	if ((c >= 'a' && c <= 'z') ||
		(c >= 'A' && c <= 'Z') ||
		(c >= '0' && c <= '9') ||
		(c == '_') || c == '.') return OPERANDS;

	for (int i = 0; i <= 18; i ++) {
		if (c == isus[i]) return OPERANDS;
	}

	if ((c == '$') ||
		(c == '^') ||
		(c == '[') ||
		(c == '@') ||
		(c == ']')) return OPERATOR;
	return ILLEGAL_CHAR; 
}

//获取字符优先级
int get_priorioty(char c) {
	if (c == '^') return 3;
	if (c == '@') return 2;
	if (c == '$') return 1;
	if (c == '[') return 0;
	return -1;
}

//将诸如a-d形式转化为a|b|c|d
string ex(string s) {
	string t;
	int l = s.size();
	for (int i = 0; i < l; i ++) {
		if (s[i] == '?' && i < l - 1 && s[i + 1] >= s[i]) {
			for (char c = s[i - 1] + 1; c <= s[i + 1]; c ++) {
				t += "$";
				t += c;
			}
			i ++;
			continue;
		}
		t += s[i];
	}
	return t;
}

//检查正则表达式,并添加&
string pretreatment(string pre_expression) {
	string treated_expression = "";

	char prechar = pre_expression[0];
	int pretype = get_chartype(prechar);
	if (pretype == ILLEGAL_CHAR) {
		cout << prechar << " is not in charset!";
		exit(0);
	}

	int len = pre_expression.size();
	treated_expression += prechar;

	for (int i = 1; i < len; i ++) {
		char nowchar = pre_expression[i];
		int nowtype = get_chartype(nowchar);
		if (nowtype == ILLEGAL_CHAR) {
			cout << nowchar << " is not in charset!";
			exit(0);
		}
		if (nowchar == '?') {
			if (i == len - 1) {
				cout << "1Format Error !!!!";
				exit(0);
			}
			char nextchar = pre_expression[i + 1]; // ab a&b ab&
			int nexttype = get_chartype(nextchar);
			if (nextchar < prechar) {
				cout << "2Format Error !!!!";
				exit(0);
			}
			for (char c = prechar + 1; c <= nextchar; c ++) {
				treated_expression += '$';
				treated_expression += c;
			}
			i ++;
			prechar = nextchar;
			pretype = nexttype;
			continue;

		}
		if ((pretype == OPERANDS || prechar == '^' || prechar == ']') &&
			(nowtype == OPERANDS || nowchar == '['))
			treated_expression += "@";
		treated_expression += nowchar;

		prechar = nowchar;
		pretype = nowtype;
	}
	return treated_expression;
}

//正则表达式中缀转后缀
string transfer(string s) {
	string t = "";

	stack<char> st;
	int len = s.size();

	for (int i = 0; i < len; i ++) {
		char c = s[i];
		int type = get_chartype(c);

		if (c == '[') st.push(c);
		else if (c == ']') {
			while (!st.empty() && st.top() != '[') {
				t += st.top();
				st.pop();
			}
			if (st.empty()) {
				cout << "Format Error !!!!";
				exit(0);
			}
			st.pop();
		} else if (type == OPERATOR) {
			int p = get_priorioty(c);
			while (!st.empty() && p <= get_priorioty(st.top())) {
				t += st.top();
				st.pop();
			}
			st.push(c);
		} else {
			t += c;
		}
	}

	while (!st.empty()) {
		if (st.top() == '[') {
			cout << "Format Error !!!!";
			exit(0);
		}
		t += st.top();
		st.pop();
	}
	return t;
}

//正则表达式转NFA
//NFA节点单元
struct Nfastate {
	char input; // 转移字符
	Nfastate* next; // 转移到的状态
	set<Nfastate*> epTrans; //空转移状态集合

	Nfastate(char c = '#', Nfastate* trans = NULL) {
		input = c;
        next = trans;
        epTrans.clear();
	}

	void add(Nfastate* n) {
		epTrans.insert(n);
	}
};



struct subNFA {
	Nfastate *head;             // 头部指针
    Nfastate *tail;             //  尾部指针

    subNFA(Nfastate* phead = NULL , Nfastate* ptail = NULL) {
        head = phead;
        tail = ptail;
    }

    subNFA(char c) {
        Nfastate *ntail = new Nfastate;
        Nfastate *nhead = new Nfastate(c, ntail);

        if(c == '#') nhead->next = NULL;

        head = nhead;
        tail = ntail;
    }
    void operator=(const subNFA& ele) {
        head = ele.head;
        tail = ele.tail;
    }
};

class NFA {
public:
	NFA(string s) {
		expression = s;
		Build_NFA();
	}
	string expression; //正则表达式
	void Build_NFA();
    Nfastate* gethead() {return subnfa.head;}
    Nfastate* gettail() {return subnfa.tail;};
private:
    subNFA subnfa;              // 最终的NFA

};


void NFA::Build_NFA() {
	string reg_expression = transfer(pretreatment(expression));
	stack<subNFA> st;

	int len = reg_expression.size();
	for (int i = 0; i < len; i ++) {
		char c = reg_expression[i];
		int type = get_chartype(c);

		if (type == OPERANDS) {
			subNFA n(c);
			st.push(n);
		} 
		//a*
		else if (c == '^') {
			if (st.empty()) {
				cout << "1Format Error !!!!";
				exit(0);
			}
			subNFA n1 = st.top();
			st.pop();

			subNFA n('#');

			(*n.head).add(n1.head);
			(*n1.tail).add(n.tail);
			(*n1.tail).add(n1.head);

			st.push(n);
		} 
		//a|b
		else if (c == '$') {
			if (st.size() < 2) {
				cout << "2Format Error !!!!";
				exit(0);
			}
			subNFA n1 = st.top();
			st.pop();
			subNFA n2 = st.top();
			st.pop();

			subNFA n('#');

			(*n.head).add(n1.head);
			(*n.head).add(n2.head);
			(*n1.tail).add(n.tail);
			(*n2.tail).add(n.tail);

			st.push(n);
		} 
		//a&b
		else if (c == '@') {
			if (st.size() < 2) {
				cout << "3Format Error !!!!";
				exit(0);
			}
			subNFA n2 = st.top();
			st.pop();
			subNFA n1 = st.top();
			st.pop();

			(*n1.tail).add(n2.head);
			n1.tail = n2.tail;

			st.push(n1);
		}
	}
	if (st.size() != 1) {
		cout << st.size();
		cout << "4Format Error !!!!";
		exit(0);
	}

	subnfa = st.top();
	st.pop();
}

//NFA转DFA
struct Dfastate {
	bool isEnd;                 //判断是否是结束状态
    set<Nfastate*> closure;     //闭包

    //通过char能到哪些节点
	Dfastate move(char c , Nfastate* tail) {
        Dfastate ret;
        for(auto x : closure) {
            if(x->input == c) ret.closure.insert(x->next);
        }
        ret.n_closure(tail);

        return ret;
    }

    void endinfo(Nfastate* tail) {
		if(closure.count(tail)) isEnd = true;
		else isEnd = false;
    }
    //求$闭包
    void n_closure(Nfastate * tail) {
    	bool hasnew = 1;
    	while (hasnew) {
    		hasnew = 0;
    		for (auto x : closure) {
    			for (auto y : x -> epTrans) {
    				if (!closure.count(y)) 
    					hasnew = 1, closure.insert(y);	
    			}
    		}
    	}
    	endinfo(tail);
    }

    bool operator<(const Dfastate& b) const {return closure < b.closure;}
    bool operator>(const Dfastate& b) const {return closure > b.closure;}
    bool operator==(const Dfastate& b) const {return closure == b.closure;}
};

struct subDFA {
	bool isEnd;
	map<int , subDFA*> to;
};

class DFA {
public:
	string expression;
	DFA(string s) {
		expression = ex(s);
		//cout << expression << "\n";
		for (int i = 0; i < (int)expression.size(); i ++) {
			int type = get_chartype(expression[i]);

			if (type == OPERANDS) {
				//cout << expression[i] << "\n";
				charset.insert(expression[i]);
			}
			if (type == ILLEGAL_CHAR) {
				cout << expression[i] << " is not in charset!";
				exit(0);
			}
		}
		Build_DFA(expression);
	}
	
	bool match(string s) {
		subDFA* nowp = dfahead;

		if (nowp == NULL) return 0;

		for (auto c : s) {
			if (!nowp->to.count(c)) return false;
			nowp = nowp->to[c];
		}
		return nowp->isEnd;
	}
	void Build_DFA(string);
	void min_DFA();
private:
	set<char> charset;
	subDFA* dfahead;

};

void DFA::Build_DFA(string expression) {
	NFA nfa(expression);
	Nfastate* head = nfa.gethead();
	Nfastate* tail = nfa.gettail();

	map<Dfastate, subDFA*> mp;
	queue<Dfastate> q;

	Dfastate T;
	T.closure.insert(head);
	T.n_closure(tail);

	mp[T] = new subDFA;
	mp[T]->isEnd = T.isEnd;

	q.push(T);
	dfahead = mp[T];

	while (!q.empty()) {
		T = q.front(); q.pop();

		subDFA* now = mp[T];
		for (auto c : charset) {
			Dfastate next = T.move(c, tail);
			if (next.closure.empty()) continue;
			if (!mp.count(next)) {
				mp[next] = new subDFA;
				mp[next]->isEnd = next.isEnd;
				q.push(next);
			}
			now->to[c] = mp[next];
		}
	}
}


void DFA::min_DFA() {
	map<subDFA*, int> mp;
	mp[dfahead] = 1;
	subDFA* nowdfa = dfahead;
	queue<subDFA*> q;
	q.push(nowdfa);
	int maxcnt = 1;
	while (!q.empty()) {
		nowdfa = q.front();
		q.pop();
		for (auto c : charset) {
			if (nowdfa->to.count(c) && !mp.count(nowdfa->to[c])) {
				subDFA* newdfa = nowdfa->to[c];
				if (newdfa->isEnd) mp[newdfa] = 0;
				q.push(newdfa); 
			} 
		}
	}
	bool hasnew = 0;
	while(hasnew) {
		if (!hasnew) break;
		for (auto c : charset) {
			set<int> v[maxn];
			for (auto dfa : mp) {
				subDFA* nowdfa = dfa.first;
				int id = dfa.second;
				if (nowdfa->to.count(c)) {
					subDFA* newdfa = nowdfa->to[c];
					if (!v[id].count(mp[newdfa])) {
						mp[nowdfa] = ++ maxcnt;
						hasnew = 1;
					}
					v[id].insert(mp[newdfa]);
				} 
			}
		}
	}
}

vector<DFA> dfa;
void makeDFA() {
	DFA dfa0("int$void$return$const$main$float$if$else");
	dfa.push_back(dfa0);
	DFA dfa1("+$-$*$/$%$=$>$<$==$<=$>=$!=$&&$||$!");
	dfa.push_back(dfa1);
	DFA dfa2("($)${$}$;$,");
	dfa.push_back(dfa2);
	DFA dfa3("[a?z$A?Z$_]$[[a?z$A?Z$_][0$1$2$3$4$5$6$7$8$9$a?z$A?Z$_]^]");
	dfa.push_back(dfa3);
	DFA dfa4("[[0$1$2$3$4$5$6$7$8$9]$[[1$2$3$4$5$6$7$8$9][0$1$2$3$4$5$6$7$8$9]^]].[[0$1$2$3$4$5$6$7$8$9]^]");
    dfa.push_back(dfa4);
	DFA dfa5("[0$1$2$3$4$5$6$7$8$9]$[[1$2$3$4$5$6$7$8$9][0$1$2$3$4$5$6$7$8$9]^]");
	dfa.push_back(dfa5);
}

void lexical() {
	for (int i = 1; i <= length; i ++) {
		string s = letter[i];
		//cout << s << "\n";
		int l = s.size();
		int start = 0;
		int cut = l;
		//cout << l << " " << cut << "\n";
		while(l) {
			if (cut <= 0) {
				cout << "Word " << s << " can not match all the DFA!!!\n";
				//return;
				//printf("Word %s can not match all the DFA\n", s);
				exit(0);
			}
			int f = 0;
			for (int j = 0; j < 6; j ++) {
				if (dfa[j].match(s.substr(start, cut))) {
					//cout << s.substr(start, cut) << "\n";
					word[++ len] = s.substr(start, cut);
					kind[len] = name[j];
					start += cut;
					l -= cut;
					f = 1;
					if (j < 3) {
						id[len] = mp[word[len]];
					} else id[len] = word[len];
					break;
				}
			}
			if (f) cut = l;
			else cut --;
		}
	}
	for (int i = 1; i <= len; i ++) {
		if (kind[i] == "INT") pdid[i] = "INT";
		else if (kind[i] == "FLOAT") pdid[i] = "FLOAT";
		else if (kind[i] == "IDN") pdid[i] = "IDN";
		else pdid[i] = word[i];
		cout << word[i] << "\t<" << kind[i] << "," << id[i] << ">\n";
		//cout << word[i] << "\t<" << kind[i] << "," << id[i] << ">" << pdid[i] << "\n";
	}
}

void test1(string fi) {
	init();
	read(fi);
	lexical();
}
//int main() {

	//freopen("out.txt", "w", stdout);
 	//test();
 	//return 0;
//}